package checkIfPangram;

import java.util.*;

public class Solution {
    public boolean checkIfPangram(String sentence) {
        // 包含每个字符至少一次
//        Set<Character> set = new HashSet<>();
//        for (int i = 0; i < sentence.length(); i++) {
//          set.add(sentence.charAt(i));
//        }
//        return set.size() == 26;
        // 位运算
        int mask = 0;
        for (int i = 0; i < sentence.length(); i++) {
            mask|=(1<<(sentence.charAt(i)-'a'));
        }
        return mask == 67108863;
    }
    public boolean isCovered(int[][] ranges, int left, int right) {
        // 差分数组
        int[] cnt = new int[52];
        for (int i = 0; i < ranges.length; i++) {
            cnt[ranges[i][0]]++;
            cnt[ranges[i][1]+1]--;
        }
        // 前缀和
        for (int i = 1; i < 52; i++) {
            cnt[i]+= cnt[i-1];
        }
        // 返回left--right
        while (left<=right){
            if(cnt[left] == 0) {
                return false;
            }
            left++;
        }
        return true;


    }
    public boolean makeEqual(String[] words) {
        //
        int[] cnt = new int[26];
        for (int i = 0; i < words.length; i++) {
            for (int j = 0; j < words[i].length(); j++) {
                cnt[words[i].charAt(j)-'a']++;
            }
        }
        for (int i = 0; i < 26; i++) {
            if(cnt[i]%words.length!=0) return false;
        }
        return true;
    }
    public int canBeTypedWords(String text, String brokenLetters) {
        String[] words = text.split(" ");
        int ans = 0;
        for (String word: words) {
            boolean can = true;
            for (int i = 0; i < brokenLetters.length(); i++) {
                if(word.contains(brokenLetters.charAt(i)+"")) {
                    can = false;
                    break;
                }
            }
            if(can) ans++;
        }
        return ans;
    }
    public int countKDifference(int[] nums, int k) {
        int ans = 0;
        int[] marks = new int[200];
        for (int i = 0; i < nums.length; i++) {
            marks[nums[i]]++;
            if(nums[i] - k >0){
                ans += marks[nums[i] - k];
            }
            ans += marks[nums[i] + k];
        }
        return ans;
    }
    public String kthDistinct(String[] arr, int k) {
        Map<String,Integer> map = new HashMap<>();
        for (int i = 0; i < arr.length; i++) {
            map.put(arr[i],map.getOrDefault(arr[i],0)+1);
        }
        for (int i = 0; i < arr.length; i++) {
            if(map.get(arr[i])==1) {
                k--;
            }
            if(k == 0) {
                return arr[i];
            }
        }
        return "";
    }
    public int countWords(String[] words1, String[] words2) {
        // 在words1中出现一次
        // 在words2中出现一次
        Map<String,Integer> map = new HashMap<>();
        for (String word: words1) {
            map.put(word,map.getOrDefault(word,0)+1);
        }
        int ans = 0;
        for (String word: words2) {
            // 如果在words1里面只出现了一次的
            if(map.getOrDefault(word,0) == 1) {
                ans++;
                map.put(word,100000);
            }else if(map.getOrDefault(word,0) == 100000) {
                ans--;
                map.put(word,1000001);
            }
        }
        return ans;
    }
    public int[] findEvenNumbers(int[] digits) {
        Set<Integer> ans = new HashSet<>();
        for (int i = 0; i < digits.length; i++) {
            for (int j = 0; j < digits.length; j++) {
                for (int k = 0; k < digits.length; k++) {
                    if(i!=j&&i!=k&&j!=k&&digits[i]!=0) {
                        if(digits[k]%2==0) {
                            ans.add(digits[i]*100+digits[j]*10+digits[k]);
                        }
                    }
                }
            }
        }
        int[] res = new int[ans.size()];
        int index = 0;
        for (int v: ans) {
            res[index++] = v;
        }
        Arrays.sort(res);
        return res;
    }
    public int[] maxSubsequence(int[] nums, int k) {
        // 找到和最大的长度为k的子序列
        PriorityQueue<Integer> pq = new PriorityQueue<>(new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o1 - o2;
            }
        });
        for (int i = 0; i < nums.length; i++) {
            //
            pq.add(nums[i]);
            if(pq.size()>k) {
                pq.poll();
            }
        }
        int[] ans = new int[k];
        while (!pq.isEmpty()) {
            // 数据结构与算法
            ans[--k] = pq.poll();
        }
        return ans;
    }
    public boolean checkValid(int[][] matrix) {
        //
        int n = matrix.length;
        for (int i = 0; i < matrix.length; i++) {
            Set<Integer> set1 = new HashSet<>();
            Set<Integer> set2 = new HashSet<>();
            for (int j = 0; j < matrix[0].length; j++) {
                set1.add(matrix[i][j]);
                set2.add(matrix[j][i]);
            }
            if(set1.size()!=n||set2.size()!=n) {
               return false;
            }
        }
        return true;
    }
    public int distMoney(int money, int children) {
        // 贪心
        // 先给每个孩子分一块
        if (money < children) {
            return -1;
        }
        money-= children;
        int cnt = Math.min(money / 7, children);
        money -= cnt * 7;
        children -= cnt;
        if ((children == 0 && money > 0) || (children == 1 && money == 3)) {
            cnt--;
        }
        return cnt;
    }
    public int findFinalValue(int[] nums, int original) {
        //
        Set<Integer> set = new HashSet<>();
        for (int i = 0; i < nums.length; i++) {
            set.add(nums[i]);
        }
        while (set.contains(original)) {
            original*=2;
        }
        return original;
    }
    public int mostFrequent(int[] nums, int key) {
        Map<Integer,Integer> map = new HashMap<>();
        int ans = 0;
        int max = 0;
        for (int i = 0; i < nums.length; i++) {
            if(nums[i] == key&&i<nums.length-1) {
                map.put(nums[i+1],map.getOrDefault(nums[i+1],0)+1);
                if(max<map.get(nums[i+1])) {
                    ans = nums[i+1];
                    max = map.get(nums[i+1]);
                }
            }
        }
        return ans;
    }
    public boolean divideArray(int[] nums) {
        //
        int[] marks = new int[501];
        int mask = 0;
        for (int num: nums) {
            mask^=num;
            marks[num]++;
        }
        if(mask != 0) {
            return false;
        }
        for (int num: nums) {
            if(num%2!=0) {
                return false;
            }
        }
        return true;
    }
    public String greatestLetter(String s) {
        int lowr = 0;
        int upper = 0;
        for (char c : s.toCharArray()) {
            if(Character.isLowerCase(c)) {
                lowr|=1<<(c-'a');
            } else {
                upper|=1<<(c-'A');
            }
        }
        // 判断有小写是否有大写
        for (int i = 0; i <= 25; i++) {
            if((lowr&upper&(1<<i))!=0) {
                return (char)(i+'A')+"";
            }
        }
        return "";
    }
    public int[] numberOfPairs(int[] nums) {
        int[] cnt = new int[101];
        for (int num: nums) {
            cnt[num]++;
        }
        int[] ans = new int[2];
        for (int t: cnt) {
            ans[0]+=t/2;
        }
        ans[1] = nums.length - ans[0];
        return ans;
    }

}
